package com.leetcode;

import com.leetcode.common.ListNode;

/**
 * 328. 奇偶链表
 * 双节点头指针
 */
public class Solution328 {

    /**
     * 简化版本
     * odd是奇数
     * even是偶数
     *
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        ListNode cur = head;

        ListNode oddHead = new ListNode(-1);
        ListNode oddCur = oddHead;

        ListNode evenHead = new ListNode(-1);
        ListNode evenCur = evenHead;

        int i = 1;
        while (cur != null) {
            if (i % 2 == 0) {
                oddCur.next = cur;
                oddCur = oddCur.next;
            } else {
                evenCur.next = cur;
                evenCur = evenCur.next;
            }
            i++;
            cur = cur.next;
        }
        oddCur.next = null;
        evenCur.next = oddHead.next;
        return evenHead.next;
    }

    public ListNode oddEvenList1(ListNode head) {
        ListNode cur = head;
        ListNode oddHead = new ListNode();
        ListNode evenHead = new ListNode();
        ListNode oddCur = oddHead;
        ListNode evenCur = evenHead;

        int i = 1;
        while (cur != null) {
            if (i % 2 == 1) {
                // 其实不需要new新的空间
                evenCur.next = new ListNode(cur.val);
                evenCur = evenCur.next;
            } else {
                oddCur.next = new ListNode(cur.val);
                oddCur = oddCur.next;
            }
            cur = cur.next;
            i++;
        }
        evenCur.next = oddHead.next;
        return evenHead.next;
    }

    public static void main(String[] args) {
        // write your code here
        ListNode head = new ListNode(1);
        ListNode cur = head;
        for (int i = 2; i <= 5; i++) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        new Solution328().oddEvenList(head);
    }

}
